#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int majorityElement(vector<int> &nums) {
    if (nums.size() == 0) {
      return -1;
    }

    int cnt = 1;
    int major = nums[0];
    for (int i = 1; i < nums.size(); i++) {
      if (cnt == 0) {
        major = nums[i];
	cnt = 1;
	continue;
      }
      if (nums[i] != major) {
        cnt--;
      } else {
        cnt++;
      }

    }
    if (cnt > 0) {
      return major;
    }

    return -1;
  }
};

int main() { return 0; }
